﻿/* Write a program that reads two integer numbers N and K and an array of N elements from the console. 
 * Find in the array those K elements that have maximal sum. */

using System;
using System.Collections.Generic;

class ReadNKFindMxSum
{
    static void Main()
    {
        uint N, K;
        bool iProvided = false;
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer greater than zero.");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);
        
        iProvided = false; //reset iProvided
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer (K must be < N).");
            else iProvided = true;
            Console.Write("Enter K: ");
        } while (UInt32.TryParse(Console.ReadLine(), out K) == false || K >= N || K < 1);

        int[] nums = new int[N];
        for (int i = 0; i < nums.Length; i++)
        {
            iProvided = false;
            do {

                if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
                else iProvided = true;
                Console.Write("Enter element {0}: ", i+1);
            } while (Int32.TryParse(Console.ReadLine(), out nums[i]) == false);
        }

        //solving using the Maximum Subarray Problem algorithm
        int MSF = nums[0], MEH = nums[0]; //declare max so far, max ending with starting element the first element
        int begin = 0, begin_temp = 0, end = 0;
        //Find sequence by looping through
        //DEPRECATED - ONLY FOR CONTIGUOUS ELEMENTS
        //for (int i = 1, a = 1; i < nums.Length; i++)
        //{
        //    //calculate MEH
        //    MEH += nums[i];
        //    if (nums[i] > MEH)
        //    {
        //        MEH = nums[i];
        //        begin_temp = i;
        //    }
        //    //calculate MSF
        //    if (MEH > MSF)
        //    {
        //        MSF = MEH;
        //        begin = begin_temp;
        //        end = i;
        //    }
        //}
        //Console.WriteLine(MSF);

        //sort using bubble sort
        for (int i = 1; i < nums.Length; i++)
        {
            for (int j = 0; j < nums.Length - i; j++)
            {
                if (nums[j] < nums[j+1])
                {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        Console.WriteLine("\r\nMaximal sum of {0} elements: ", K);
        int total = 0;
        string elements = null;
        //array is already sorted, count first K (highest) elements and output them
        for (int i = 0; i < K; i++) 
        {
            total += nums[i];
            elements += nums[i];
            if (i < K - 1) elements += ", ";
        }
        Console.WriteLine("Total: {0}\r\nNumbers: {1}", total, elements);
        Console.WriteLine(
            );
        //Console.WriteLine(N);
        //Console.WriteLine(K);
    }
}
